Sparse Matrix multiplication

Time: O(MxNxL); Space: O(MxL); medium

Given two sparse matrices A and B, return the result of AxB.

You may assume that A’s column number is equal to B’s row number.

Example 1:

Input: A =

[
  [ 1, 0, 0],
  [-1, 0, 3]
]

B =

[
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

Output:

[
    [ 7, 0, 0 ],
    [ -7 0 3 ]
]

Explanation:

     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
     |  0 0 1 |

Notes:

  • A is MxN matrix

  • B is NxL matrix

1. Naive

Algorithm * Initialize the result matrix * for each element, compute the dot product of the corresponding row from A and column from B This is a triple for loop, O(N^3)

Improvements: * Take advantage of the sparsity. * When we see a zero, no need to add anything ??? (when a[i,k]==0, then no need to add b[k,j]) to condition on this, we need to iterate on i, k. so swap the for loop Complxity: sparse –> only 2 for loops

[4]:

class Solution1(object):
    def multiply(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
        m, n, l = len(A), len(A[0]), len(B[0])
        res = [[0 for _ in range(l)] for _ in range(m)]

        for i in range(m):
            for k in range(n):
                if A[i][k]:
                    for j in range(l):
                        res[i][j] += A[i][k] * B[k][j]

        return res

[5]:

s = Solution1()
A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]
B = [
  [7, 0, 0],
  [0, 0, 0],
  [0, 0, 1]
]
assert s.multiply(A, B) == [
    [ 7, 0, 0],
    [-7, 0, 3]
]